1. Field of the Invention
The present invention relates to a parity generation circuit, a counter circuit, and a counting method.
2. Description of the Related Art
A population count refers to counting the number of ‘1’s in binary data, and some central processing units (CPUs) is configured to issue a population count (POPC) instruction to perform the counting.
The POPC instruction, formerly implemented by software emulation and not as an instruction set because of its low frequency of use, has been frequently used in recent years to calculate a hamming distance (the number of bits that differ between two bit strings). To increase the instruction processing speed, the POPC instruction is increasingly implemented by hardware. For example, Japanese Patent Application Laid-open No. 2005-165793 discloses a conventional technology to realize a circuit that executes the POPC instruction.
To improve reliability, a CPU is used that ensures the validity of data using a parity added to operation input/output data. When such CPU executes a POPC instruction by hardware, how to obtain the parity of the operation result of the POPC instruction becomes an issue.
Assume, for example, that the population count is performed using the above conventional technology, and that the parity of the operation result is calculated later using another circuit. In this case, the instruction processing time is prolonged by the time taken to calculate the parity. This reduces the effect of implementing the POPC instruction by hardware to process the instruction at high speed. Therefore, to avoid affecting the cycle time required for the operation, the parity needs to be calculated in the cycle time equal to or less than that of the operation. To accomplish this, the parity of the result of the POPC instruction needs to be predicted from input data.
To obtain the parity of the operation result without increasing the time taken to process the POPC instruction, the parity needs to be predicted by a separate circuit in parallel with the population count. This parity prediction is required to predict the parity of the operation result from the input data of the POPC instruction and its parity.